//
//  main.cpp
//  FastSort
//
//  Created by chenyh on 2021/2/22.
//

#include <iostream>
using namespace std;
/**
 快速排序：时间复杂度在0(nlog2n)并且是一种就地排序算法，其时间复杂度和 空间复杂度都是比较优秀的。
 
 5.3.1 算法描述
 快速排序算法是 C.A.R Hoarse 提出的一种算法，该算法是目前实践中使用最频繁、实 践效率最好的排序算法。快速排序是一种运用分治思想的算法，它的主要思想是:有待排 序数组 S={d1,d2,d3,...,dn}，从中找出元素 v，我们称之为划界元素，将剩下的元素中小于或等于 v 的元素移动到 v 的前面，将大于或等于 v 的元素移动到 v 的后面，这样 v 就找到了 它最终的排序位置，并将 S 分划为两个不相交的子数组 S1 和 S2。其中 S1 中的元素均小于 或等于 v，即 S1={x∈S–{v} | x ≤ v};S2 中的元素均大于或等于 v，即 S2={x∈S–{v} | x ≥ v}。这样的过程称为一次排序。然后，快速排序算法递归地在子序列 S1 和 S2 上进行上述 的排序过程，直到所有的子序列都只包含 0 个或 1 个元素时停止。这样整个数组就排序完 成了。
 根据上面的描述，可以将快速排序的过程归纳为下面 4 个步骤。
 (1)取某个元素 v 作为待排序数组 S 的划界元素。
 (2)移动元素，将 S–{v}(S 中除去 v 的元素集)划分成两个不相交的子序列 S1 和 S2，
 满足 S1 中的元素都小于或等于 v，S2 中的元素大于或等于 v。 (3)返回 v 的位置。
 (4)递归地在 S1 和 S2 上进行上述 3 个步骤。

 从理论上讲，划界元素的选择没有限制，但是在实践中我们一般采用 3 种方式:即选 择待排序元素中的第 1 个元素，或选择待排序元素中的最后那个元素，或选择待排元素中 居中的那个元素。为了阐述方便，下面的讨论中我们采用第 2 种方式，即选取待排序元素 中的最后那个元素 dn 作为划界元素。由于快速排序是就地排序，所以递归结束之后不需要 进行合并操作。
 假设有待排数组 S={49,55,25,97,60,27,49,50}，我们按照上面的过程对它进行快速排序， 其过程如图 5-7 所示。我们观察一次排序的过程。我们设置变量 p 和 r 表示数组的首尾元 素下标，选取数组最右边的元素 50 为我们第一次排序的划界元素，记为 S[r]。那么我们就 需要将 S[p]，S[p+1]，...，S[r–1]组成的序列进行子序列划分。首先，我们设置变量 i=p–1， 即最前面元素的前一个，设置变量 j = p。反复执行如下步骤:
 (1)执行 j+1，如果 S[j]≤S[r]，交换 S[i+1]与 S[j]的值，i=i+1，j=j+1;如果 S[j]≥S[r]， i 不变，j=j+1;
 (2)到 j=r–1 时，停止步骤(1)。
 重复执行上述步骤直至停止后，交换 S[i+1]与 S[r]的值，划界元素放在了其最终位置
 上，其左边的元素均小于等于它，右边的元素均大于它。
 从图 5-7 所示的过程我们可以发现，快速排序可以一次就将划界元素放置到它的最终
 位置上，实际上，很多情况下，快速排序可以一次确定 2 个甚至 3 个元素的最终位置(包 括划界元素)。
 注意:快速排序是一个不稳定的排序算法，主要是因为在进行最后一步划界元素与 S[i+1]交换的时候有可能打破前面元素的稳定性。读者可以设想这样一种情况， 在某趟排序过程的最后一步，划界元素与元素 a 交换，如果原数组中包含两个 a 值元素，则可能经过交换，原本在前面的 a 值元素交换到了另一个同值元素的后面。
 
 */

template <class T>
void exchange(T *a,T *b)
{
    T temp = *a;
    *a = *b;
    *b = temp;
}
/**

第一趟：
 49 55 25 97 60 27 49 50  i=-1 j=0  初始数据
 1: 49 i=0 j=1
 2: 49 25 55   i=1 j=2
 3: 49 25 27 49 50 55 97 60
得到划界位置：4
然后开始递归划界：0-3 （4） 5-7

 在进行快速排序时，如果参加排序的元素原本就是有序的，这时候快速排序的时间效 率最低，时间复杂度为 O(n2)。因为第一趟排序中，我们需要进行 n–1 次比较动作，而且最 后一个元素将放置到原位置;第二趟排序中，我们需要进行 n–2 次比较，倒数第 2 个元素 放置原位置;以次类推，我们总共需要进行比较的次数为(n–1)+(n–2)+(n–3)+...+1=n(n–1)/2 次。每次比较的时间复杂度为 T(1)=1，所以在这种情况下，快速排序的时间复杂度为 T(n)=T(1)*n(n–1)/2=O(n2)。
 快速排序在其最好情况下效率是非常高的。当我们每趟递归排序后，划界元素正好在 序列的中间或者所划分的两个子序列长度相当，此时每个子序列的长度都被减半，所需比 较的次数大大降低，快速排序的时间复杂度为:≤ (log2n)n+nT(1) = O(nlog2n)
 在通常情况下，快速排序的时间复杂度也比较好，为 O(nlog2n)，与最好情况接近
 */


template <class T>
int  partition(T data[],int p,int r) {
    T temp = data[r];   //初始化划界元素为最终位置
    int i = p-1;        //初始化i为首部之前的元素
    for (int j=p; j<r; j++) {
        if (data[j] > temp) { //发现小于划界元素的键值时，交换元素i+1和元素j的值
            i+=1;
            exchange(&data[i],&data[j]);
        }
    }
    exchange(&data[i+1], &data[r]);
    return i+1;
}


/**
 运行结果如图 5-8 所示。
 【例 5-6】 编写一个 C++程序，将数组{2,5,7,8,3,6,11,24,0,1}按从大到小的顺序排列。 【分析】我们刚才给出的算法是将数据从小到大升序排列，现
  在我们需要进行降序排列，需要修改算法。通过算法我们可以分析 到，决定数据是升序还是降序排列的操作主要是我们对数据进行比 较从而划分子序列的时候，所以我们只需要更改上面算法中的 partition()函数，就可以实现。
 */

template <class T>
int partitionl(T data[],int p,int r) {

/**    {2,5,7,8,3,6,11,24,0,1,24,23};
    {
 i = 12
 j = 11
 p = 0
 23 > 2 i = 11
 24 > 2 i = 10
 24 > 2 i = 9 j = 7  {24,5,7,8,3,6,11,2d,0,1,24,23};
 
        
    }
 */
    T temp = data[p];
    int i = r+1;
    for (int j=r; j>p; j--) {
        if (data[j] <= temp) { //发现小于划界元素的键值时
            i-=1;             //交换元素 i+1 和元素 j 的值
            exchange(&data[i], &data[j]);
        }
    }
    exchange(&data[i-1], &data[p]);
    return i-1;
}


template <class T>
void quickSort(T data[],int p,int r) {
    int position = 0;
    if (p < r) {
        position = partitionl(data, p, r);   //返回划界元素的最终位置
        quickSort(data, p, position-1);     //对划分的子序列进行排序
        
        quickSort(data, position+1, r);
    }
}


int main(int argc, const char * argv[]) {
    // insert code here...
    int data[] = {2,5,7,8,3,6,11,24,0,1,24,23};
    int length = 12;
    for(int i = 0;i<length;i++)
        cout<<data[i]<<" ";
    cout<<endl;
    quickSort(data,0,11);
    for(int i = 0;i<length;i++)
        cout<<data[i]<<" ";
    cout<<endl;
    return 0;

}
